As wireless technology provides faster and more inexpensive devices, it enables people to be more mobile. Such mobility is desirable to many because it enables better collaboration and more efficient transactions.
To improve the performance of wireless devices, and hence improve mobility, designers are turning to the use of multiple-input multiple-output (“MIMO”) systems. MIMO systems have more than one transmitter and more than one receiver, and hence, more than one wireless channel. Such systems work well with existing orthogonal frequency-division multiplexing (“OFDM”) methods of transmission because the orthogonal nature of the carriers helps to prevent interference between the adjacent carriers.
At any given frequency, channel output y is related to channel input s by a matrix H such that:y=H s+n,   (1)where s, y and n are vectors. The input vector s has MT elements and the output vector y and noise vector n has MR elements. MT and MR are the number of transmit and receive transceivers, respectively. Input vector s is a member of a signal constellation having MT dimensions (ΩMT). Because of this dimensionality, the decoding problem may become computationally demanding. For example, an algorithm to decode y in order to determine which constellation point ŝ was sent over the wireless channel requires solving the equation
                              s          ^                =                                                            arg                            ⁢              min                                      s              ∈                              Ω                                  M                  T                                                              ⁢                                                                                      y                  -                  Hs                                                            2                        .                                              (        2        )            This problem has complexity that grows exponentially with the number of transmit transceivers MT. For instance, with 4 transmit transceivers (MT=4) using 16-QAM, there are in each symbol interval 164 or 65,536 constellation points in each frequency bin to be searched in order to locate the signal. Any reduction in this complexity would be advantageous.